package com.sheng.leetcode.year2023.month07.day26;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/07/26
 * <p>
 * 2569. 更新数组后处理求和查询<p>
 * <p>
 * 给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作：<p>
 * 操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。<p>
 * 操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。<p>
 * 操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。<p>
 * 请你返回一个数组，包含所有第三种操作类型的答案。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]<p>
 * 输出：[3]<p>
 * 解释：第一个操作后 nums1 变为 [1,1,1] 。第二个操作后，nums2 变成 [1,1,1] ，所以第三个操作的答案为 3 。所以返回 [3] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]<p>
 * 输出：[5]<p>
 * 解释：第一个操作后，nums2 保持不变为 [5] ，所以第二个操作的答案是 5 。所以返回 [5] 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums1.length,nums2.length <= 10^5<p>
 * nums1.length = nums2.length<p>
 * 1 <= queries.length <= 10^5<p>
 * queries[i].length = 3<p>
 * 0 <= l <= r <= nums1.length - 1<p>
 * 0 <= p <= 10^6<p>
 * 0 <= nums1[i] <= 1<p>
 * 0 <= nums2[i] <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/handling-sum-queries-after-update">2569. 更新数组后处理求和查询</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2569 {

    @Test
    public void test01() {
//        int[] nums1 = {1, 0, 1}, nums2 = {0, 0, 0};
//        int[][] queries = {{1, 1, 1}, {2, 1, 0}, {3, 0, 0}};
        int[] nums1 = {1}, nums2 = {5};
        int[][] queries = {{2, 0, 0}, {3, 0, 0}};
        System.out.println(Arrays.toString(new Solution().handleQuery(nums1, nums2, queries)));
    }
}


class Solution {
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        int m = nums1.length;
        int ansSz = 0;
        for (int[] query : queries) {
            if (query[0] == 3) {
                ++ansSz;
            }
        }
        long[] ans = new long[ansSz];

        SegTree st = new SegTree();
        // 建树，由于 i 不会重复，并且叶子节点默认 cnt 为 0，因此不用额外写建树函数，直接套用 toggle 即可
        for (int i = 0; i < m; ++i) {
            if (nums1[i] == 1) {
                st.toggle(i, i, 0, m - 1, st.root);
            }
        }

        // 初始化 nums2 的累加和 sum
        long sum = 0;
        for (int i = 0; i < m; ++i) {
            sum += nums2[i];
        }

        int ptr = 0;
        for (int[] query : queries) {
            if (query[0] == 1) { // 操作 1：在线段树中翻转区间 [l, r]
                int l = query[1], r = query[2];
                st.toggle(l, r, 0, m - 1, st.root);
            } else if (query[0] == 2) { // 操作 2：得到 nums1 中数字 1 的总数，乘以 p 加到 sum 中
                int all = st.root.cnt, p = query[1];
                sum = sum + 1L * all * p;
            } else {   // 操作 3：双指针法将 sum 添加到 ans 中
                ans[ptr++] = sum;
            }
        }
        return ans;
    }
}

class Node {
    Node left = null;
    Node right = null;
    int cnt = 0;
    boolean toggled = false;    // 懒标记，表示该区间的孩子是否翻转
}

class SegTree {
    public Node root = new Node();

    // 翻转区间 [l, r]
    void toggle(int l, int r, int s, int e, Node node) {
        if (l <= s && e <= r) {   // 如果线段 [s, e] 位于区间 [l, r] 内部
            node.cnt = e - s + 1 - node.cnt;    // 翻转，即将 cnt 更新为线段长度 - cnt
            node.toggled = !node.toggled;   // 更新懒标记
            return;
        }
        int m = (s + e) >> 1;
        pushdown(node, s, e);
        if (l <= m) {
            toggle(l, r, s, m, node.left);
        }
        if (m + 1 <= r) {
            toggle(l, r, m + 1, e, node.right);
        }
        node.cnt = node.left.cnt + node.right.cnt;
    }

    // 动态开点 + 懒标记下推
    void pushdown(Node node, int s, int e) {
        if (node.left == null) {
            node.left = new Node();
        }
        if (node.right == null) {
            node.right = new Node();
        }
        if (!node.toggled) {
            return;
        }
        int m = (s + e) >> 1;
        node.left.cnt = m - s + 1 - node.left.cnt;
        node.right.cnt = e - (m + 1) + 1 - node.right.cnt;
        node.left.toggled = !node.left.toggled;
        node.right.toggled = !node.right.toggled;
        node.toggled = false;
    }

    // 得到区间 [l, r] 中数字 1 的个数。本题中用不到，因为只需要访问根节点的 cnt 即可
    int query(int l, int r, int s, int e, Node node) {
        if (l <= s && e <= r) {
            return node.cnt;
        }
        int m = (s + e) >> 1, ret = 0;
        pushdown(node, s, e);
        if (l <= m) {
            ret += query(l, r, s, m, node.left);
        }
        if (m + 1 <= r) {
            ret += query(l, r, m + 1, e, node.right);
        }
        return ret;
    }
}

// 暴力破解超时
//class Solution {
//    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
//        // 1, l, r：将 nums1 从下标 l 到下标 r 的所有 0 反转成 1，或将 1 反转成 0
//        // 2, p, 0：对于 0 <= i < n 中，nums2[i] = num2[i] + nums1[i] * p
//        // 3, 0, 0：求 nums2 中所有元素的和
//        List<Long> list = new ArrayList<>();
//        long[] nums = new long[nums2.length];
//        for (int i = 0; i < nums2.length; i++) {
//            nums[i] = nums2[i];
//        }
//        for (int[] query : queries) {
//            if (query[0] == 1) {
//                for (int i = query[1]; i <= query[2]; i++) {
//                    nums1[i] = (nums1[i] + 1) % 2;
//                }
//            } else if (query[0] == 2) {
//                int p = query[1];
//                for (int i = 0; i < nums.length; i++) {
//                    nums[i] = nums[i] + nums1[i] * p;
//                }
//            } else {
//                long sum = 0;
//                for (long i : nums) {
//                    sum += i;
//                }
//                list.add(sum);
//            }
//        }
//        return list.stream().mapToLong(Long::valueOf).toArray();
//    }
//}
